#define  _CRT_SECURE_NO_WARNINGS 1



#include <iostream>
#include <vector>
#include <queue>
using namespace std;



// 415. 字符串相加
//class Solution {
//public:
//    string addStrings(string num1, string num2)
//    {
//        int index = 0, i = num1.size() - 1, j = num2.size() - 1;
//
//        string ans;
//        while (i >= 0 || j >= 0)
//        {
//            int ret = index;
//            index = 0;
//
//            if (i < num1.size())
//            {
//                ret += num1[i] - '0';
//                i--;
//            }
//
//            if (j < num2.size())
//            {
//                ret += num2[j] - '0';
//                j--;
//            }
//
//            if (ret >= 10)
//            {
//                ret %= 10;
//                index = 1;
//            }
//
//            ans += to_string(ret);
//        }
//
//        if (index)
//            ans += '1';
//
//        reverse(ans.begin(), ans.end());
//
//        if (ans.empty())
//            ans += "";
//
//        return ans;
//    }
//};




//LCR 076. 数组中的第 K 个最大元素

//class Solution {
//public:
//    int findKthLargest(vector<int>& nums, int k)
//    {
//        map<int, int, greater<int>> m1;
//
//        //1，统计次数
//        for (auto e : nums)
//        {
//            m1[e]++;
//        }
//
//        for (auto e : m1)
//        {
//            int num = e.second;
//            while (num)
//            {
//                num--;
//                k--;
//
//                if (k == 0)
//                    return e.first;
//            }
//        }
//
//        return -1;
//    }
//};







//思路
//1, 两个堆， 大堆A (保存小的一半元素)， 小堆B（保存大的一半元素），
//2，新增操作，保证A和B的元素均匀分配，相差不超过1， 
//3, 新增操作, 看A和B的元素之和，
//4，为偶数， 新增到A里面， 保证 0 == A - B <= 1, 我们先插入B， 然后拿出B的最小的元素插入A 
//5, 为奇数, 新增到B里面， 我们先插入A里面， 然后从堆顶拿出最大的值插入B

class MedianFinder {
public:
    priority_queue<int> _pqA;
    priority_queue<int, vector<int>, greater<int>> _pqB;
    int n = 0;

    MedianFinder() {
    }

    void addNum(int num)
    {
        if (n % 2 == 0) //为偶数的情况， 插入到A里面
        {
            _pqB.push(num);
            int top = _pqB.top();
            _pqB.pop();

            _pqA.push(top);
        }
        else  //为奇数的情况，插入到B里面
        {
            _pqA.push(num);
            int top = _pqA.top();
            _pqA.pop();

            _pqB.push(top);
        }

        n++;
    }

    double findMedian()
    {
        if (n % 2 == 0)
        {
            return (_pqA.top() + _pqB.top()) / 2.0;
        }
        else
        {
            return _pqA.top();
        }
    }
};
